package com.dy.查找.动态表查找.平衡二叉树;

/**
 * 左子树和右子树都是平衡二叉树，且左右子树深度差不超过1，平衡因子是深度之差，只可以是-1 0 1
 * <p>
 * 对于不平衡的
 */

import com.dy.树与二叉树.二叉树.链式存储.BiTree;
import com.dy.树与二叉树.二叉树.链式存储.BiTreeNode;

/**
 * LL型         左孩子的左孩子添加节点,单向右旋
 * RR型         右孩子的右孩子添加节点，单向左旋
 * LR型         左孩子的右孩子添加节点，先左旋再右旋
 * RL型         右孩子的左孩子添加节点，先右旋再左旋
 */
public class AVL {
    public static void main(String[] args) {
        AVL avl = new AVL();
        BiTreeNode root=new BiTreeNode(10);
        root= insert(root,20);
        root=insert(root,5);
        root=insert(root,3);
        root=insert(root,7);
        root=insert(root,9);
        root=insert(root,2);
        root=insert(root,30);
       root=insert(root,25);
//        System.out.println(root.height);
//        root.lchild = new BiTreeNode(5);
//        root.rchild = new BiTreeNode(23);
//        root.rchild.lchild = new BiTreeNode(22);
//        root.rchild.rchild = new BiTreeNode(24);
//        root.rchild.rchild.rchild = new BiTreeNode(25);
        BiTree roo = new BiTree(root);
        System.out.println("***************");
        roo.levelTraverse(roo.root);
        System.out.println("***************");
//        System.out.println("***************");
//        root = RR(root);
//        roo = new BiTree(root);
//        roo.levelTraverse(roo.root);
    }
    //LL型，右旋

    /**
     * 20
     * 19
     * 18
     *
     * @param
     * @return
     */
    public static int getHeight(BiTreeNode node) {
        if (node == null) {
            return 0;
        } else return node.height;
    }

    public static void updateHeight(BiTreeNode node) {
        node.height = Math.max(getHeight(node.rchild), getHeight(node.lchild)) + 1;
    }
//右旋
    public static BiTreeNode LL(BiTreeNode node) {
        //先得到左孩子
        BiTreeNode lchild = node.lchild;
        //原根的现左孩子是左孩子的右孩子
        node.lchild = lchild.rchild;
        //左孩子的右孩子是根
        lchild.rchild = node;

        updateHeight(node);
        updateHeight(lchild);

        //调整高度

        //返回新的根
        return lchild;
    }

    /**
     * 20
     * 5     23
     * 22   24
     *
     * @param node 25
     * @return
     */
    //RR型，左旋
    public static BiTreeNode RR(BiTreeNode node) {
        //先得到右孩子
        BiTreeNode rchild = node.rchild;

        node.rchild = rchild.lchild;

        rchild.lchild = node;
        updateHeight(node);
        updateHeight(rchild);
        return rchild;

    }

    //LR,先对左孩子左旋，再对根右旋
    public static BiTreeNode LR(BiTreeNode node) {
        //先得到左孩子左旋

        node.lchild = RR(node.lchild);
        return LL(node);

    }

    //RL,先对右孩子节点右旋，再对根左旋
    public static BiTreeNode RL(BiTreeNode node) {
        //先得到右孩子右旋

        node.rchild = LL(node.rchild);
        return RR(node);

    }

    public static BiTreeNode insert(BiTreeNode root, int data) {
        //如果为空，则添加
        if (root == null) {
            root = new BiTreeNode(data);
            return root;
        }
        //如果相同，则什么也不做
        else if (data == (int) root.data) {
            return root;
        } else {
            if (data < (int) root.data) {
                root.lchild =insert(root.lchild,data);
                updateHeight(root);
                if(getHeight(root.lchild)-getHeight(root.rchild)==2){
                    if(data<(int)root.lchild.data){
                        return  LL(root);
                    }
                    else{
                        return  LR(root);
                    }
                }

            }
            else if(data>(int)root.data){
                root.rchild=insert(root.rchild,data);
                updateHeight(root);
                if(getHeight(root.lchild)-getHeight(root.rchild)==-2){
                    if(data<(int)root.rchild.data){
                        return RL(root);
                    }
                    else{
                        return RR(root);
                    }
                }
            }
        }
        return root;


    }
//    public static BiTreeNode remove(BiTreeNode root,int key){
//        if(root==null) return null;
//        if((int)root.data>key){
//            root.lchild = remove(root.lchild,key);
//
//        }
//        else if((int)root.data<key){
//            root.rchild = remove(root.rchild,key);
//        }
//    }
}
